package tree;

/**
 * Created by lizhenyu on 2019/9/19
 *
 * description 用字典树解决字符串公共子前缀问题
 */
public class TrieTree {

    /**
     * 创建字典树
     *
     * @param root
     * @param str
     */
    public void createTree(TrieTreeNode root, String str) {
        if(str == null || str.length() == 0) {
            return;
        }
        char[] arr = str.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            int mKey = arr[i] - 'a';    // 存放字典索引
            if (root.childs[mKey] == null) {
                // 该索引节点不存在，直接创建
                root.childs[mKey] = new TrieTreeNode(arr[i]);
            } else {
                // 节点存在，计数加1
                root.childs[mKey].count += 1;
            }
            // 顺着当前节点，往下创建子节点
            root = root.childs[mKey];
        }
    }

    /**
     * 前缀长度计数
     */
    public int findCount(TrieTreeNode root, String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return -1;
        }
        char[] arr = prefix.toCharArray();
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            int mKey = arr[i] - 'a';    // 存放字典索引
            if (root.childs[mKey] == null) {
                // 只要一个字符没出现，则该前缀的字符串没有出现，计数为0
                return 0;
            } else {
                count = root.childs[mKey].count;
                root = root.childs[mKey];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String[] strs = { "banana", "band", "bee", "abcolute", "acm" };
        String[] prefix = { "ba", "b", "band", "abc" };

        TrieTree tree = new TrieTree();
        TrieTreeNode root = new TrieTreeNode('-');

        // 依次输入每个字符串，创建字典树
        for (String s : strs) {
            tree.createTree(root, s);
        }

        for (String pre : prefix) {
            int num = tree.findCount(root, pre);
            System.out.println(pre + " " + num);
        }
    }
}

/**
 * 多叉树节点类
 */
class TrieTreeNode{
    char value;    // 节点字符
    int count;     // 节点字符出现次数
    TrieTreeNode[] childs;
    final int MAX_SIZE = 26;
    TrieTreeNode (char x) {
        this.value = x;
        this.count = 1;
        this.childs = new TrieTreeNode[MAX_SIZE];
    }
}